const int maxn=17;
typedef int LL;
class Solution {
public:
    vector<LL>v[maxn];
    int minimumDifference(vector<int>& nums) {
        int n=nums.size()/2;
        LL all=1LL<<n;
        for(int i=0;i<all;++i){
            LL sum=0;LL res=0;
            for(int j=0;j<n;++j){
                if((1LL<<j)&i){
                    sum+=nums[j];
                    res++;
                }
                else{
                    sum-=nums[j];
                }
            }
            v[res].push_back(sum);
        }
        for(int i=0;i<maxn;i++) sort(v[i].begin(),v[i].end());
        
        vector<int>a;
        auto it=a.begin();
        a.insert(it,nums.begin()+n,nums.end());
        /// abs ( sumA(+ -)+sumB(+ -) ) min
        /// sumA+sumB>=0最小 ----> sumA>=-sumB --> -sumB<=sumA 即对此时的sumB取负后二分找到第一个大于等于的
        LL ans=INT_MAX;
        for(int i=0;i<all;++i){
            LL res=0;LL temp=i;
            bitset<17>s(i);
            res=s.count();
            LL sum=0;
            for(int j=0;j<n;++j){
                if((1LL<<j)&i){
                    sum+=a[j];
                }
                else sum-=a[j];
            }
            int cnt=n-res;
            //二分   
            int l=0; int r=v[cnt].size()-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(v[cnt][mid]>=-sum) r=mid;
                else l=mid+1;
            }
            ans=min(ans,abs(sum+v[cnt][l]));
        }
        return ans;
    }
};